#ifndef __HASHINDEX_H__
#define __HASHINDEX_H__

//#define USE_HASHINDEX_16

/*
===============================================================================

Fast hash table for indexes and arrays.
Does not allocate memory until the first key/index Pair is added.

===============================================================================
*/

namespace inf {

    template< typename Type, int Max, int NullIndex, int DEFAULT_HASH_SIZE, int DEFAULT_HASH_GRANULARITY >
    class HashIndexBase {
    public:
        static const int MaxValue = Max;
        static const int NULL_INDEX = NullIndex;

                        HashIndexBase( void );
                        HashIndexBase( const int initialHashSize, const int initialIndexSize );
                        ~HashIndexBase( void );

        HashIndexBase &	operator=( const HashIndexBase &other );

        // returns a key for a string
        int				generate_key( const char *string, bool caseSensitive = true ) const;
        // returns a key for a vector
//        int				generate_key( const Vec3 &v ) const;
        // returns a key for two integers
        int				generate_key( const unsigned int n1, const unsigned int n2 ) const;
        // returns a key for a single integer
        int				generate_key( const int n ) const;
        // returns a key a pointer Type					
        int				generate_key( const void* n ) const;

        size_t			total_size( void ) const;                 // returns total size of allocated memory including size of hash index Type
        size_t			allocated( void ) const;            // returns total size of allocated memory
        size_t			reduced_allocated( void ) const;

        // get size of hash table
        int				get_hash_size( void ) const;
        // get size of the index
        int				get_index_size( void ) const;
        // returns number in the range [0-100] representing the spread over the hash table
        int				get_spread( void ) const;

        // get the first index from the hash, returns NULL_INDEX if empty hash entry
        int				get_first( const int key ) const;
        // get the next index from the hash, returns NULL_INDEX if at the end of the hash chain
        int				get_next( const int index ) const;

        // add an index to the hash, assumes the index has not yet been added to the hash
        void			add( const int key, const int index );
        // remove an index from the hash
        void			remove( const int key, const int index );
        // insert an entry into the index and add it to the hash, increasing all indexes >= index
        void			insert_index( const int key, const int index );
        // remove an entry from the index and remove it from the hash, decreasing all indexes >= index
        void			remove_index( const int key, const int index );

        // clear the hash
        void			clear( void );
        // clear and resize
        void			clear( const int newHashSize, const int newIndexSize );
        // free allocated memory
        void			free( void );
        // allocate memory, only used internally
        void			allocate( const int newHashSize, const int newIndexSize );
        // set granularity
        void			set_granularity( const int newGranularity );
        // force resizing the index, current hash table stays intact
        void			resize_index( const int newIndexSize );


        void			swap( HashIndexBase &rhs );

        bool			verify_self( void );
    public:
        void			init( const int initialHashSize, const int initialIndexSize );

    private:
        int				hashSize;
        Type*			hash;
        int				indexSize;
        Type*			indexChain;
        int				granularity;
        int				hashMask;

        void invariant_check_bounds( void ) {
            assert( (hashSize < MaxValue) && (indexSize < MaxValue) && "size too big" );
        }
    };

    /*
    ================
    HashIndexBase::HashIndexBase
    ================
    */
    template< typename Type, int Max, int NullIndex, int DEFAULT_HASH_SIZE, int DEFAULT_HASH_GRANULARITY >
    HashIndexBase< Type, Max, NullIndex, DEFAULT_HASH_SIZE, DEFAULT_HASH_GRANULARITY >::HashIndexBase( void ) {
            init( DEFAULT_HASH_SIZE, 0 );
    }

    /*
    ================
    HashIndexBase::HashIndexBase
    ================
    */
    template< typename Type, int Max, int NullIndex, int DEFAULT_HASH_SIZE, int DEFAULT_HASH_GRANULARITY >
    HashIndexBase< Type, Max, NullIndex, DEFAULT_HASH_SIZE, DEFAULT_HASH_GRANULARITY >::HashIndexBase( const int initialHashSize, const int initialIndexSize ) {
            init( initialHashSize, initialIndexSize );
    }

    /*
    ================
    HashIndexBase::~HashIndexBase
    ================
    */
    template< typename Type, int Max, int NullIndex, int DEFAULT_HASH_SIZE, int DEFAULT_HASH_GRANULARITY >
    HashIndexBase< Type, Max, NullIndex, DEFAULT_HASH_SIZE, DEFAULT_HASH_GRANULARITY >::~HashIndexBase( void ) {
            free();
    }

    /*
    ================
    HashIndexBase::init
    ================
    */
    template< typename Type, int Max, int NullIndex, int DEFAULT_HASH_SIZE, int DEFAULT_HASH_GRANULARITY >
    void HashIndexBase< Type, Max, NullIndex, DEFAULT_HASH_SIZE, DEFAULT_HASH_GRANULARITY >::init( const int initialHashSize, const int initialIndexSize ) {
            assert( math::is_power_of_two( initialHashSize ) );

            hashSize = initialHashSize;
            hash = NULL;
            indexSize = initialIndexSize;
            indexChain = NULL;
            invariant_check_bounds();
            granularity = DEFAULT_HASH_GRANULARITY;
            hashMask = hashSize - 1;
    }

    /*
    ================
    HashIndexBase::allocate
    ================
    */
    template< typename Type, int Max, int NullIndex, int DEFAULT_HASH_SIZE, int DEFAULT_HASH_GRANULARITY >
    void HashIndexBase< Type, Max, NullIndex, DEFAULT_HASH_SIZE, DEFAULT_HASH_GRANULARITY >::allocate( const int newHashSize, const int newIndexSize ) {
            assert( math::is_power_of_two( newHashSize ) );

            free();
            hashSize = newHashSize;
            hash = new Type[hashSize];
            memory_set( hash, 0xff, hashSize * sizeof( hash[0] ) );
            indexSize = newIndexSize;
            indexChain = new Type[indexSize];
            invariant_check_bounds();
            memory_set( indexChain, 0xff, indexSize * sizeof( indexChain[0] ) );
            hashMask = hashSize - 1;
    }

    /*
    ============
    HashIndexBase::free
    ============
    */
    template< typename Type, int Max, int NullIndex, int DEFAULT_HASH_SIZE, int DEFAULT_HASH_GRANULARITY >
    void HashIndexBase< Type, Max, NullIndex, DEFAULT_HASH_SIZE, DEFAULT_HASH_GRANULARITY >::free( void ) {
            delete[] hash;
            hash = NULL;
            delete[] indexChain;
            indexChain = NULL;
    }

    /*
    ================
    HashIndexBase::resize_index
    ================
    */
    template< typename Type, int Max, int NullIndex, int DEFAULT_HASH_SIZE, int DEFAULT_HASH_GRANULARITY >
    void HashIndexBase< Type, Max, NullIndex, DEFAULT_HASH_SIZE, DEFAULT_HASH_GRANULARITY >::resize_index( const int newIndexSize ) {
            Type *oldIndexChain;
            int mod, newSize;

            if ( newIndexSize <= indexSize ) {
                return;
            }

            mod = newIndexSize % granularity;
            if ( !mod ) {
                newSize = newIndexSize;
            } else {
                newSize = newIndexSize + granularity - mod;
            }

            if ( indexChain == NULL ) {
                indexSize = newSize;
                return;
            }

            oldIndexChain = indexChain;
            indexChain = new Type[newSize];
            memory_copy( indexChain, oldIndexChain, indexSize * sizeof( indexChain[0] ) );
            memory_set( indexChain + indexSize, 0xff, (newSize - indexSize) * sizeof( indexChain[0] ) );
            delete[] oldIndexChain;
            indexSize = newSize;
            invariant_check_bounds();
    }

    /*
    ================
    HashIndexBase::get_spread
    ================
    */
    template< typename Type, int Max, int NullIndex, int DEFAULT_HASH_SIZE, int DEFAULT_HASH_GRANULARITY >
    int HashIndexBase< Type, Max, NullIndex, DEFAULT_HASH_SIZE, DEFAULT_HASH_GRANULARITY >::get_spread( void ) const {
            int i, index, totalItems, average, error, e;
            Type *numHashItems;

            if ( hash == NULL ) {
                return 100;
            }

            totalItems = 0;
            numHashItems = new Type[hashSize];
            for ( i = 0; i < hashSize; i++ ) {
                numHashItems[i] = 0;
                for ( index = hash[i]; index >= 0; index = indexChain[index] ) {
                    numHashItems[i]++;
                }
                totalItems += numHashItems[i];
            }
            // if no items in hash
            if ( totalItems <= 1 ) {
                delete[] numHashItems;
                return 100;
            }
            average = totalItems / hashSize;
            error = 0;
            for ( i = 0; i < hashSize; i++ ) {
                e = math::abs( numHashItems[i] - average );
                if ( e > 1 ) {
                    error += e - 1;
                }
            }
            delete[] numHashItems;
            return 100 - (error * 100 / totalItems);
    }

    /*
    ================
    HashIndexBase::add
    ================
    */
    template< typename Type, int Max, int NullIndex, int DEFAULT_HASH_SIZE, int DEFAULT_HASH_GRANULARITY >
    void HashIndexBase< Type, Max, NullIndex, DEFAULT_HASH_SIZE, DEFAULT_HASH_GRANULARITY >::add( const int key, const int index ) {
            int h;

            assert( index >= 0 );
            if ( hash == NULL ) {
                int size = ( index >= indexSize ? index + 1 : indexSize ) + granularity - 1;
                allocate( hashSize, size - size % granularity );
            } else if ( index >= indexSize ) {
                resize_index( index + 1 );
            }

            h = key & hashMask;

#ifdef _DEBUG
            int oldChain	= indexChain[ index ];
            int oldHash		= hash[ h ];
#endif
            assert( oldChain == NULL_INDEX && oldHash != index );

            indexChain[ index ] = hash[h];
            hash[ h ] = index;
    }

    /*
    ================
    HashIndexBase::allocated
    ================
    */
    template< typename Type, int Max, int NullIndex, int DEFAULT_HASH_SIZE, int DEFAULT_HASH_GRANULARITY >
    size_t HashIndexBase< Type, Max, NullIndex, DEFAULT_HASH_SIZE, DEFAULT_HASH_GRANULARITY >::allocated( void ) const {
            size_t total = 0;
            if( hash ) {
                total += hashSize * sizeof( hash[ 0 ] );
            }
            if(indexChain) {
                total += indexSize * sizeof( indexChain[ 0 ] );
            }
            return total;
    }

    /*
    ================
    HashIndexBase::total_size
    ================
    */
    template< typename Type, int Max, int NullIndex, int DEFAULT_HASH_SIZE, int DEFAULT_HASH_GRANULARITY >
    size_t HashIndexBase< Type, Max, NullIndex, DEFAULT_HASH_SIZE, DEFAULT_HASH_GRANULARITY >::total_size( void ) const {
            return sizeof( *this ) + allocated();
    }

    /*
    ================
    HashIndexBase::operator=
    ================
    */
    template< typename Type, int Max, int NullIndex, int DEFAULT_HASH_SIZE, int DEFAULT_HASH_GRANULARITY >
    HashIndexBase< Type, Max, NullIndex, DEFAULT_HASH_SIZE, DEFAULT_HASH_GRANULARITY >& HashIndexBase< Type, Max, NullIndex, DEFAULT_HASH_SIZE, DEFAULT_HASH_GRANULARITY >::operator=( const HashIndexBase &other ) {
            if( &other == this ) {
                return *this;
            }

            granularity = other.granularity;
            hashMask = other.hashMask;

            delete[] hash;
            hash = NULL;

            delete[] indexChain;
            indexChain = NULL;

            hashSize = other.hashSize;
            indexSize = other.indexSize;
            invariant_check_bounds();

            if ( other.hash ) {
                hash = new Type[hashSize];
                memory_copy( hash, other.hash, hashSize * sizeof( hash[0] ) );
            }
            if ( other.indexChain ) {
                indexChain = new Type[indexSize];
                memory_copy( indexChain, other.indexChain, indexSize * sizeof( indexChain[0] ) );
            }

            return *this;
    }

    /*
    ================
    HashIndexBase::remove
    ================
    */
    template< typename Type, int Max, int NullIndex, int DEFAULT_HASH_SIZE, int DEFAULT_HASH_GRANULARITY >
    void HashIndexBase< Type, Max, NullIndex, DEFAULT_HASH_SIZE, DEFAULT_HASH_GRANULARITY >::remove( const int key, const int index ) {
            int k = key & hashMask;

            if ( hash == NULL ) {
                return;
            }
            if ( hash[k] == index ) {
                hash[k] = indexChain[index];
            }
            else {
                for ( int i = hash[k]; i != NULL_INDEX; i = indexChain[i] ) {
                    if ( indexChain[i] == index ) {
                        indexChain[i] = indexChain[index];
                        break;
                    }
                }
            }
            indexChain[index] = NULL_INDEX;
    }

    /*
    ================
    HashIndexBase::get_first
    ================
    */
    template< typename Type, int Max, int NullIndex, int DEFAULT_HASH_SIZE, int DEFAULT_HASH_GRANULARITY >
    int HashIndexBase< Type, Max, NullIndex, DEFAULT_HASH_SIZE, DEFAULT_HASH_GRANULARITY >::get_first( const int key ) const {
            return hash ? hash[ key & hashMask ] : NULL_INDEX;
    }

    /*
    ================
    HashIndexBase::get_next
    ================
    */
    template< typename Type, int Max, int NullIndex, int DEFAULT_HASH_SIZE, int DEFAULT_HASH_GRANULARITY >
    int HashIndexBase< Type, Max, NullIndex, DEFAULT_HASH_SIZE, DEFAULT_HASH_GRANULARITY >::get_next( const int index ) const {
            assert( index >= 0 && index < indexSize );
            return indexChain ? indexChain[ index ] : NULL_INDEX;
    }

    /*
    ================
    HashIndexBase::insert_index
    ================
    */
    template< typename Type, int Max, int NullIndex, int DEFAULT_HASH_SIZE, int DEFAULT_HASH_GRANULARITY >
    void HashIndexBase< Type, Max, NullIndex, DEFAULT_HASH_SIZE, DEFAULT_HASH_GRANULARITY >::insert_index( const int key, const int index ) {
            int i, max;

            if ( hash != NULL ) {
                max = index;
                for ( i = 0; i < hashSize; i++ ) {
                    if ( hash[i] >= index ) {
                        hash[i]++;
                        if ( hash[i] > max ) {
                            max = hash[i];
                        }
                    }
                }
                for ( i = 0; i < indexSize; i++ ) {
                    if ( indexChain[i] >= index ) {
                        indexChain[i]++;
                        if ( indexChain[i] > max ) {
                            max = indexChain[i];
                        }
                    }
                }
                if ( max >= indexSize ) {
                    resize_index( max + 1 );
                }
                for ( i = max; i > index; i-- ) {
                    indexChain[i] = indexChain[i-1];
                }
                indexChain[index] = NULL_INDEX;
            }
            add( key, index );
    }

    /*
    ================
    HashIndexBase::remove_index
    ================
    */
    template< typename Type, int Max, int NullIndex, int DEFAULT_HASH_SIZE, int DEFAULT_HASH_GRANULARITY >
    void HashIndexBase< Type, Max, NullIndex, DEFAULT_HASH_SIZE, DEFAULT_HASH_GRANULARITY >::remove_index( const int key, const int index ) {
            int i, max;

            remove( key, index );
            if ( hash != NULL ) {
                max = index;
                for ( i = 0; i < hashSize; i++ ) {
                    if ( hash[i] >= index ) {
                        if ( hash[i] > max ) {
                            max = hash[i];
                        }
                        hash[i]--;
                    }
                }
                for ( i = 0; i < indexSize; i++ ) {
                    if ( indexChain[i] >= index ) {
                        if ( indexChain[i] > max ) {
                            max = indexChain[i];
                        }
                        indexChain[i]--;
                    }
                }
                for ( i = index; i < max; i++ ) {
                    indexChain[i] = indexChain[i+1];
                }
                indexChain[max] = NULL_INDEX;
            }
    }

    /*
    ================
    HashIndexBase::clear
    ================
    */
    template< typename Type, int Max, int NullIndex, int DEFAULT_HASH_SIZE, int DEFAULT_HASH_GRANULARITY >
    void HashIndexBase< Type, Max, NullIndex, DEFAULT_HASH_SIZE, DEFAULT_HASH_GRANULARITY >::clear( void ) {
            if ( hash != NULL ) {
                memory_set( hash, 0xff, hashSize * sizeof( hash[0] ) );
            }
            if ( indexChain != NULL ) {
                memory_set( indexChain, 0xff, indexSize * sizeof( indexChain[0] ) );
            }
    }

    /*
    ================
    HashIndexBase::clear
    ================
    */
    template< typename Type, int Max, int NullIndex, int DEFAULT_HASH_SIZE, int DEFAULT_HASH_GRANULARITY >
    void HashIndexBase< Type, Max, NullIndex, DEFAULT_HASH_SIZE, DEFAULT_HASH_GRANULARITY >::clear( const int newHashSize, const int newIndexSize ) {
            free();
            hashSize = newHashSize;
            indexSize = newIndexSize;
            invariant_check_bounds();
    }

    /*
    ================
    HashIndexBase::get_hash_size
    ================
    */
    template< typename Type, int Max, int NullIndex, int DEFAULT_HASH_SIZE, int DEFAULT_HASH_GRANULARITY >
    int HashIndexBase< Type, Max, NullIndex, DEFAULT_HASH_SIZE, DEFAULT_HASH_GRANULARITY >::get_hash_size( void ) const {
            return hashSize;
    }

    /*
    ================
    HashIndexBase::get_index_size
    ================
    */
    template< typename Type, int Max, int NullIndex, int DEFAULT_HASH_SIZE, int DEFAULT_HASH_GRANULARITY >
    int HashIndexBase< Type, Max, NullIndex, DEFAULT_HASH_SIZE, DEFAULT_HASH_GRANULARITY >::get_index_size( void ) const {
            return indexSize;
    }

    /*
    ================
    HashIndexBase::set_granularity
    ================
    */
    template< typename Type, int Max, int NullIndex, int DEFAULT_HASH_SIZE, int DEFAULT_HASH_GRANULARITY >
    void HashIndexBase< Type, Max, NullIndex, DEFAULT_HASH_SIZE, DEFAULT_HASH_GRANULARITY >::set_granularity( const int newGranularity ) {
            assert( newGranularity > 0 );
            granularity = newGranularity;
    }

    /*
    ================
    HashIndexBase::generate_key
    ================
    */
    template< typename Type, int Max, int NullIndex, int DEFAULT_HASH_SIZE, int DEFAULT_HASH_GRANULARITY >
    int HashIndexBase< Type, Max, NullIndex, DEFAULT_HASH_SIZE, DEFAULT_HASH_GRANULARITY >::generate_key( const char *string, bool caseSensitive ) const {
        return ( Str::hash( string ) & hashMask, caseSensitive );
    }

    /*
    ================
    HashIndexBase::generate_key
    ================
    */
    //template< typename Type, int Max, int NullIndex, int DEFAULT_HASH_SIZE, int DEFAULT_HASH_GRANULARITY >
    //int HashIndexBase< Type, Max, NullIndex, DEFAULT_HASH_SIZE, DEFAULT_HASH_GRANULARITY >::generate_key( const Vec3 &v ) const {
    //        return ( ( math::ftoi( v[0] ) + math::ftoi( v[1] ) + math::ftoi( v[2] ) ) & hashMask );
    //}

    /*
    ================
    HashIndexBase::generate_key
    ================
    */
    template< typename Type, int Max, int NullIndex, int DEFAULT_HASH_SIZE, int DEFAULT_HASH_GRANULARITY >
    int HashIndexBase< Type, Max, NullIndex, DEFAULT_HASH_SIZE, DEFAULT_HASH_GRANULARITY >::generate_key( const unsigned int n1, const unsigned int n2 ) const {
            return ( ( n1 + n2 ) & hashMask );
    }

    /*
    ================
    HashIndexBase::generate_key
    ================
    */
    template< typename Type, int Max, int NullIndex, int DEFAULT_HASH_SIZE, int DEFAULT_HASH_GRANULARITY >
    int HashIndexBase< Type, Max, NullIndex, DEFAULT_HASH_SIZE, DEFAULT_HASH_GRANULARITY >::generate_key( const int n ) const {
            return n & hashMask;
    }

    /*
    ================
    HashIndexBase::generate_key
    ================
    */
    template< typename Type, int Max, int NullIndex, int DEFAULT_HASH_SIZE, int DEFAULT_HASH_GRANULARITY >
    int HashIndexBase< Type, Max, NullIndex, DEFAULT_HASH_SIZE, DEFAULT_HASH_GRANULARITY >::generate_key( const void* n ) const {
            return ( ( ( UINT_PTR ) n ) & hashMask );
    }

    /*
    ================
    HashIndexBase::verify_self
    ================
    */
    template< typename Type, int Max, int NullIndex, int DEFAULT_HASH_SIZE, int DEFAULT_HASH_GRANULARITY >
    bool HashIndexBase< Type, Max, NullIndex, DEFAULT_HASH_SIZE, DEFAULT_HASH_GRANULARITY >::verify_self( void ) {
            int i, j;
            int c;
            int count = get_hash_size();
            for ( i = 0; i < count; i++ ) {
                for ( c = get_first( i ), j = 0; c != NULL_INDEX && j < get_index_size(); j++, c = get_next( c ) ) {
                }
                if ( j == get_index_size() ) {
                    return false;
                }
            }
            return true;
    }

    /*
    ================
    HashIndexBase::swap
    ================
    */
    template< typename Type, int Max, int NullIndex, int DEFAULT_HASH_SIZE, int DEFAULT_HASH_GRANULARITY >
    void HashIndexBase< Type, Max, NullIndex, DEFAULT_HASH_SIZE, DEFAULT_HASH_GRANULARITY >::swap( HashIndexBase &rhs ) {
            iswap( hashSize, rhs.hashSize );
            iswap( hash, rhs.hash );
            iswap( indexSize, rhs.indexSize );
            iswap( indexChain, rhs.indexChain );
            iswap( granularity, rhs.granularity );
            iswap( hashMask, rhs.hashMask );
    }

    typedef HashIndexBase< short, math::LIMITS_SHORT_MAX, -1, 256, 256 > HashIndexShort;
    typedef HashIndexBase< unsigned short, math::LIMITS_UNSIGNED_SHORT_MAX - 1, math::LIMITS_UNSIGNED_SHORT_MAX, 256, 256 > HashIndexUShort;
    typedef HashIndexBase< int, math::LIMITS_INTEGER_MAX, -1, 1024, 1024 > HashIndexInt;

#ifdef USE_HASHINDEX_16
    typedef HashIndexShort HashIndex;
#else
    typedef HashIndexInt HashIndex;
#endif


}   // ::inf

#endif /* !__HASHINDEX_H__ */
